/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/binary-tree-maximum-node
   @Language: C++
   @Datetime: 17-04-01 20:43
   */

/* Definition of Binary TreeNode
 * struct TreeNode{
 *     int val;
 *	   TreeNode *left, *right;
 *	   TreeNode(int val=-1){
 *         this->val = val;
 *         left = right = NULL;
 *     }
 * };
 */

class Solution {
public:
	/**
	 * @param root the root of binary tree
	 * @return the max node
	 * Tip: Find left-branch max and right-branch max
	 *      get maximum (l,r,root)
	 */
	TreeNode* maxNode(TreeNode* root) {
		// Write your code here
		if (root==NULL) return NULL;
		TreeNode *l = maxNode(root->left);
		TreeNode *r = maxNode(root->right);
		if (l) root = (root->val>l->val ? root : l);
		if (r) root = (root->val>r->val ? root : r);
		return root;
	}
};
